package dp;

import java.util.Arrays;

public class leetcode91 {

    /**
     * 记忆化搜索＋递归
     * @param s
     * @return
     */
    public int numDecodings2(String s) {
        int n=s.length();
        int[] dp=new int[n+1];//dp[i]表示从下标i开始解码的解法数量
        Arrays.fill(dp,-1);
        return ff1(s,0,dp);
    }
    static int ff1(String s,int i,int[] dp){
        int length = s.length();
        //如果i等于length,说明到了末尾,收集到了一种结果,返回1
        if(i==length)return 1;
        //如果这种情况收集过了(dp[i]已经解决)
        if(dp[i]!=-1)return dp[i];
        char c=s.charAt(i);//获取当前字符，如果是0，该解码不存在
        int t=c-'0';
        if(t==0) {dp[i]=0;return 0;}//从i开始解码方法为0
        dp[i]=ff1(s,i+1,dp);
        if(i+1<length&&(t*10+(s.charAt(i+1)-'0'))<=26){
            dp[i]+=ff1(s,i+2,dp);
        }
        return dp[i];
    }

    /**
     * dp动态规划
     */
    public int numDecodings(String s) {
        int n=s.length();
        int[] dp=new int[n+1];//dp[i]表示从下标i开始解码的解法数量
        //默认初始化为0
        dp[n]=1;
        //从后往前递推
        for(int i=n-1;i>=0;i--){
            //获取当前字符
            char c=s.charAt(i);
            int t=c-'0';
            //对于从i开始的解法
                 //如果i为0,从i开始的解码方法为0
            if(t==0)dp[i]=0;
            else{
                dp[i]=dp[i+1];
                if(i+1<n&&(t*10+(s.charAt(i+1)-'0'))<=26)dp[i]+=dp[i+2];
            }
        }
        return dp[0];
    }

}
